#include <bits/stdc++.h>
using namespace std;

/*
3266. K 次乘运算后的最终数组 II
已解答
困难
相关标签
相关企业
提示
给你一个整数数组 nums ，一个整数 k  和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
将 x 替换为 x * multiplier 。
k 次操作以后，你需要将 nums 中每一个数值对 109 + 7 取余。

请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。

 

示例 1：

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2

输出：[8,4,6,5,6]

解释：

操作	结果
1 次操作后	[2, 2, 3, 5, 6]
2 次操作后	[4, 2, 3, 5, 6]
3 次操作后	[4, 4, 3, 5, 6]
4 次操作后	[4, 4, 6, 5, 6]
5 次操作后	[8, 4, 6, 5, 6]
取余操作后	[8, 4, 6, 5, 6]
示例 2：

输入：nums = [100000,2000], k = 2, multiplier = 1000000

输出：[999999307,999999993]

解释：

操作	结果
1 次操作后	[100000, 2000000000]
2 次操作后	[100000000000, 2000000000]
取余操作后	[999999307, 999999993]
 

提示：

1 <= nums.length <= 104
1 <= nums[i] <= 109
1 <= k <= 109
1 <= multiplier <= 106
*/

// 法一
class Solution {
    const int MOD = 1'000'000'007; // 取模基数，防止数值溢出

    // 快速幂算法：计算 x^n % MOD
    long long pow(long long x, int n) {
        long long res = 1;
        for (; n; n /= 2) {
            if (n % 2) {
                res = res * x % MOD; // 奇数时累乘当前基数
            }
            x = x * x % MOD;         // 基数平方迭代
        }
        return res;
    }

public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        if (multiplier == 1) { // 乘数为1时直接返回原数组（优化特例）
            return move(nums);
        }

        int n = nums.size();
        int mx = *max_element(nums.begin(), nums.end()); // 获取数组当前最大值
        
        // 预处理阶段：计算每个二进制位需要的乘方次数
        vector<pair<int, long long>> e_pow_m; // 存储（指数e, multiplier^e）
        long long pow_m = 1;                  // 当前乘方值
        int e = 0;                            // 对应的指数
        for (int pow2 = 1; pow2 <= mx; pow2 <<= 1) { // 遍历二进制位
            // 当乘方值不足当前二进制位时，累乘multiplier
            if (pow_m < pow2) { 
                pow_m *= multiplier;
                e++;
            }
            e_pow_m.emplace_back(e, pow_m); // 记录对应二进制位的乘方参数
        }

        vector<pair<long long, int>> h(n);   // 带索引的元素数组
        for (int i = 0; i < n; i++) {
            h[i] = {nums[i], i};            // 初始化元素及其原始索引
        }
        auto clone = h;                     // 备份原始数据（用于回退暴力模拟）

        // 阶段一：将元素提升到当前最大值级别
        int left = k;                       // 剩余可操作次数
        int mx_clz = __builtin_clz(mx);     // 计算前导零数量（用于位运算优化）
        for (int i = 0; i < n && left >= 0; i++) {
            // 根据元素值的二进制位获取预计算的乘方参数
            int bit_pos = __builtin_clz(nums[i]) - mx_clz;
            auto [e, pow_m] = e_pow_m[bit_pos];
            
            long long x = nums[i];
            // 调整乘方次数边界条件（确保精确提升到目标级别）
            if (pow_m / multiplier * x >= mx) { // 多操作一次的情况
                pow_m /= multiplier;
                e--;
            } else if (x * pow_m < mx) {        // 少操作一次的情况
                pow_m *= multiplier;
                e++;
            }
            
            left -= e;          // 扣除已用操作次数
            h[i].first *= pow_m; // 应用乘方提升
        }

        // 剩余操作次数不足时回退暴力模拟
        if (left < 0) {
            h = move(clone);    // 还原原始数据
            // 构建最小堆进行逐次操作（时间复杂度O(k log n)）
            std::make_heap(h.begin(), h.end(), greater<>());
            while (k--) {
                std::pop_heap(h.begin(), h.end(), greater<>());
                h.back().first = h.back().first * multiplier % MOD; // 取模防止溢出
                std::push_heap(h.begin(), h.end(), greater<>());
            }
            // 回写结果到原数组
            for (auto& [x, j] : h) {
                nums[j] = x % MOD;
            }
            return move(nums);
        }

        // 阶段二：批量分配剩余操作次数（数学优化）
        k = left;
        long long pow1 = pow(multiplier, k / n);     // 基础乘方
        long long pow2 = pow1 * multiplier % MOD;   // 额外多一次乘方
        
        // 快速选择排序（O(n)复杂度，替代完全排序）
        std::nth_element(h.begin(), h.begin() + k % n, h.end());  // 区分前k%n个元素
        
        // 按分配策略应用乘方
        for (int i = 0; i < n; i++) {
            auto& [x, j] = h[i];
            // 前k%n个元素多乘一次（利用快速选择结果）
            nums[j] = x % MOD * (i < k % n ? pow2 : pow1) % MOD;
        }
        return move(nums);
    }
};